#include<stdio.h>
#include<stdlib.h>

//查找表的定义
#define LIST_SIZE 20
typedef int KeyType;
typedef struct
{    
	KeyType key;
}RecordType;

typedef struct 
{    
	RecordType r[LIST_SIZE+1];    
	int length;}
RecordList;//查找表类型

//顺序查找（哨兵）
int SeqSearch(RecordList l,KeyType k)
{    
	l.r[0].key=k;
	int i=l.length;    
	while(l.r[i].key!=k)i--;    
	return i;
}

//冒泡排序，用于对查找表进行排序
void bubbleSort(RecordList *l) 
{
	for (int i=1;i<l->length;i++)
	{        
		for (int j=1;j<=l->length-i;j++) 
		{            
			if(l->r[j].key>l->r[j+1].key) 
			{                
				RecordType temp=l->r[j]; 
				l->r[j]=l->r[j+1];
				l->r[j+1]=temp;            
			}        
		}    
	}
}

//二分查找（非递归）
int BinSrch(RecordList l,KeyType k)
{    
	int low=1;    
	int high=l.length;    
	while(low<=high)    
	{        
		int mid=(low+high)/2;
		if(k==l.r[mid].key)return mid;
		else if(k<l.r[mid].key)high=mid-1;        
		else low=mid+1;    
	}    
	return 0;
}

//二分查找（递归）
int BinSrch1(RecordList l,KeyType k,int low,int high)
{    
	if(low>high)return 0;    
	int mid=(low+high)/2;    
	if(k==l.r[mid].key) return mid;    
	else if(k<l.r[mid].key) return BinSrch1(l,k,low,mid-1);    
	else return BinSrch1(l,k,mid+1,high);
}

//菜单
void menu()
{    
	printf("请选择查找方式：\n");    
	printf("1.顺序查找（哨兵）\n");    
	printf("2.二分查找（非递归）\n");    
	printf("3.二分查找（递归）\n");    
	printf("0.退出\n");
}

//查找表创建
void createList(RecordList *l)
{    
	printf("请输入查找表中元素的个数（不超过%d)",LIST_SIZE);
	scanf("%d",&l->length);
	for(int i=1;i<=l->length;i++)
	{        
		printf("请输入第%d个元素：",i);        
		scanf("%d",&l->r[i].key);
	}
}

int main()
{    
	RecordList L;
	KeyType k;
	int choice;
	int result;    
	int Binresult;    
	int Binresult1;    
	while(1)    
	{        
		menu();        
		scanf("%d",&choice);        
		switch(choice)        
		{                        
			case 1:                
			    createList(&L);                
			    printf("请输入你要查找的元素：");                
			    scanf("%d",&k);                
			    result=SeqSearch(L,k);                
			    if(result!=0)                
			    {printf("查找成功，元素在第%d个位置\n",result);}                
			    else                
			    {printf("查找失败\n");}                
			    break;            
			case 2:                 
			    createList(&L);                
			    bubbleSort(&L);
			    printf("排序后的数组：");
			    for(int i=1; i<=L.length; i++) 
				{
				   printf("%d ", L.r[i].key);
			    }
			    printf("请输入你要查找的元素：");                
			    scanf("%d",&k);                
			    Binresult=BinSrch(L,k);               
			    if(Binresult!=0)                
			    {printf("查找成功，元素在第%d个位置\n",Binresult);}                
			    else                
			    {printf("查找失败\n");}                
			    break;            
			case 3:               
			    createList(&L);                
			    bubbleSort(&L); 
			    printf("排序后的数组：");
			    for(int i=1; i<=L.length; i++) {
				    printf("%d ", L.r[i].key);
			    }
			    printf("请输入你要查找的元素：");                
			    scanf("%d",&k);                
			    Binresult1=BinSrch1(L,k,1,L.length);                
			    if(Binresult1!=0)                \
			    {printf("查找成功，元素在第%d个位置\n",Binresult1);}                
			    else                
			    {printf("查找失败\n");}                
			    break;            
			case 0:                
			    printf("程序退出\n");                
			    exit(0);            
			default:                
			    printf("选择无效，请重新选择\n");        
		}    
	}    
	return 0;
}

